class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        rows=len(matrix)
        cols=len(matrix[0])
        up=[[0]*cols for _ in range(rows)]
        for i in range(cols):
            count=0
            for j in range(rows):
                    count= count+1 if matrix[j][i]=="1" else 0
                    up[j][i]=count
        #print(up)
        area=0
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j]=="1":
                    k=j
                    while k>=0 and up[i][j]>0:
                        area=max(area,(j-k+1)*min(up[i][k:j+1]))
                        k-=1
        return area
                
'''
优化的暴力解法会超时
'''

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        rows=len(matrix)
        cols=len(matrix[0])
        up=[[0]*cols for _ in range(rows)]
        for i in range(cols):
            count=0
            for j in range(rows):
                    count= count+1 if matrix[j][i]=="1" else 0
                    up[j][i]=count
        #print(up)
        area=0
        def findmax(heights,cols):
            left,right=[0]*cols,[cols]*cols
            stack=[]
            for i in range(cols):
                while stack and heights[i]<=heights[stack[-1]]:
                    right[stack[-1]]=i
                    stack.pop()
                left[i]=stack[-1] if stack else -1
                stack.append(i)
            ans = max((right[i] - left[i] - 1) * heights[i] for i in range(cols))
            return ans
        for i in range(rows):
            area=max(area,findmax(up[i],cols))
        return area
    

'''
执行用时：
88 ms
, 在所有 Python3 提交中击败了
81.39%
的用户
内存消耗：
20.3 MB
, 在所有 Python3 提交中击败了
5.11%
的用户
'''